package com.wxx;

import java.util.Arrays;

/**
 * @author: Jetwang
 * @date: 2022/3/19 19:31
 * @description: GenericInsertionSort 通用插入排序
 * @version: 1.0
 */
public class GenericInsertionSort {
    public static <T extends Comparable<T>> void insertionSort(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j-1].compareTo(arr[j]) > 0) {
                    swap(arr, j, j-1);
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 对插入排序进行优化   交换元素改为赋值
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<T>> void insertionSort2(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 将arr[i] 插入到合适的位置
            T t = arr[i];
            int j;
            for (j = i; j > 0; j--) {
                if (arr[j-1].compareTo(t) > 0) {
                    // 往后平移
                    arr[j] = arr[j-1];
                } else {
                    break;
                }
            }
            arr[j] = t;
        }
    }

    /**
     * 提取数字交换方法
     * @param arr
     * @param i
     * @param j
     */
    private static <T> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



    public static void main(String[] args) {
        Integer[] arr = {2, 5, 1, 6, 3};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
        Integer[] arr02 = {2, 7, 9, 6, 3};
        insertionSort2(arr02);
        System.out.println(Arrays.toString(arr02));
    }
}
